﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
namespace MoPhongThuatToan
{
    class Kruskal:CANHNA
    {
        private int n;
        private int[,] a = new int[100, 100];
        private CANHNA[] T = new CANHNA[10000];
        private int nT;
	    private int[] label=new int[10000];
	    private CANHNA[] Edge=new CANHNA[10000];
	    private int nE;
        public void NhapFile(String FilePath)
        {
            FileStream fs = new FileStream(FilePath, FileMode.Open);
            StreamReader sr = new StreamReader(fs);
            n = Convert.ToInt32(sr.ReadLine());
            for (int i = 0; i < n; i++)
            {
                string Line = sr.ReadLine();
                string[] G = Line.Split(new char[] { ' ' });
                for (int j = 0; j < n; j++)
                {
                    a[i, j] = int.Parse(G[j]);
                }
            }
            sr.Close();
            fs.Close();
        }
        public void XuatFile(string FilePath)
        {
            FileStream fs = new FileStream(FilePath, FileMode.Create);
            StreamWriter sw = new StreamWriter(fs);
            sw.WriteLine(n);
            //for (int i = 0; i < n; i++)
            //{
            //    for (int j = 0; j < n; j++)
            //    {
            //        sw.Write(a[i, j]);
            //        sw.Write("\t");
            //    }
            //    sw.Write("\n");
            //    sw.Write(sw.NewLine);
            //}
            int kq=KruskalAlg();
            //sw.WriteLine(nT);
            //sw.Write("\n");
            int temp = 0;
            if (kq == 1)
            {
                for (int i = 0; i < nT; i++)
                {
                    sw.Write(T[i].GetDinh1() + 1);
                    sw.Write("==>");
                    sw.Write(T[i].GetDinh2() + 1);
                    sw.Write("\n");
                    //sw.Write(T[i].GetTS());
                    temp += T[i].GetTS();
                }
                sw.Write(temp);
            }
            sw.Close();
            fs.Close();
        }
        public void KhoiTaoKruskal()
        {
	        int k=0;
	        for(int i=0;i<n;i++)
	        {
		        for(int j=i+1;j<n;j++)
			        if(a[i,j]!=0)
			        {
                        Edge[k] = new CANHNA();
				        Edge[k].SetDinh1(i+1);
				        Edge[k].SetDinh2(j+1);
				        Edge[k].SetTS(a[i,j]);
				        k++;
			        }
	        }
	        nE=k;
	        for(int i=0;i<n;i++)
		        label[i]=i;
	        SapTang();
        }
        public void HoanVi(ref CANHNA a,ref CANHNA b)
        {
            CANHNA temp=new CANHNA();
            temp=a;
            a=b;
            b=temp;
        }
        public void SapTang()
        {
	        for(int i=0;i<nE;i++)
		        for(int j=i+1;j<nE;j++)
			        if(Edge[i].GetTS()>Edge[j].GetTS())
			        {
				        HoanVi(ref Edge[i],ref Edge[j]);
			        }
        }
        public void UpdateLabel(int v1,int v2)
        {
            int min = label[v1];
            int max = label[v2];

            if (min > max)
            {
                max = label[v1];
                min = label[v2];
            }
	        for(int i=0;i<n;i++)
		        if(label[i]==max)
			        label[i]=min;
        }
        public int KruskalAlg()
        {
	        nT=0;
	        KhoiTaoKruskal();
	        for(int i=0;i<nE;i++)
	        {
                CANHNA Ed = new CANHNA();
                Ed=Edge[i];
		        int v1=Ed.GetDinh1();
		        int v2=Ed.GetDinh2();
		        if(label[v1]!=label[v2])
		        {
			        T[nT++]=Ed;
			        UpdateLabel(v1,v2);
		        }
		        if(nT==(n-1))
			        break;
	        }
            if (nT == (n - 1))
                return 1;
            return 0;
        }
    }
}
